package com.maishi.programmer.digui;

import static com.sun.org.apache.xalan.internal.lib.ExsltMath.power;

/**
 * Created by brossdong on 2018/3/22.
 * 给定一个double类型的浮点数base和int类型的整数exponent。
 * 求base的exponent次方
 */
public class TestErjinzhi16 {

    /**
     * 使用递归
     * 时间复杂度:O(logn)
     * 当n为偶数，a^n =（a^n/2）*（a^n/2）
     * 当n为奇数，a^n = a^[(n-1)/2] * a^[(n-1)/2] * a
     */
    public static double Power(double base, int exponent) {

        int n = Math.abs(exponent);

        if (n == 0) return 1;
        if (n == 1) return base;

        double result = 0.0;

        result = power(base, n >> 1);
        result *= result;

        //如果n为奇数
        if ((n & 1) == 1) result *= base;

        //如果指数为负数，则应该求result的倒数
        if (exponent < 0) result = 1 / result;

        return result;
    }

    public static void main(String[] args) {
        double power = Power(2, -1);
        System.out.println(power);
    }
}
